import java.util.Deque;
import java.util.LinkedList;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-02-20
 * Time: 22:35
 */
public class Sort {
    //冒泡排序
    //时间复杂度：不要考虑优化 O(N^2)   n*(n-1)
    //空间复杂度：O(1)
    //稳定性：稳定
    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            boolean flag = false;
            for (int j = 0; j < array.length-i-1; j++) {
                if(array[j] > array[j+1]) {
                    swap(array,j,j+1);
                    flag = true;
                }
            }
            if(flag == false) {
                return;
            }
        }
    }

    private static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    private static void insertSort(int[] array,int left,int right) {
        for(int i = left+1; i <= right; i++) {
            int tmp = array[i];
            int j = i-1;
            for(; j >= left; j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    //array[j+1] = tmp;
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

    //快速排序
    //时间复杂度：O(N*log(N)) 最好情况
    //最坏情况：有序的 n^2 或者逆序 (没有左右树)
    //空间复杂度：最好(满、完全二叉树 均匀分割) O(logN)
    //最坏 O(N)
    //稳定性：不稳定
    //可能会异常 溢出
    public static void  quickSort(int[] array) {
        quick(array,0,array.length-1);
    }

    private static void quick(int[] array,int start,int end) {

        //三数取中法
        int index = midTree(array,start,end);
        swap(array,index,start);
        //为什么去大于号
        if(start >= end) { //细节注意！
            return;
        }

        if(end - start + 1 <= 14) {
            //直接插入排序(基本有序了) 减少递归的次数
            insertSort(array,start,end);
        }

        int pivot = partition2(array,start,end); //划分
        //左边
        quick(array,start,pivot-1);
        //右边
        quick(array,pivot+1,end);
    }

    private static int partition(int[] array,int left,int right) {
        int tmp = array[left];
        while (left < right) {
            while(left < right && array[right] >= tmp) {
                right--;
            }
            array[left] = array[right];
            while(left < right && array[left] <= tmp) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }

    //Hoare法
    private static int partition1(int[] array,int left,int right) {
        int tmp = array[left];
        int i = left;
        while (left < right) {
            while(left < right && array[right] >= tmp) {
                right--;
            }
            while(left < right && array[left] <= tmp) {
                left++;
            }
            swap(array,left,right);
        }
        swap(array,left,i);
        return left;
    }


    //前后指针法(了解即可)
    private static int partition2(int[] array,int left,int right) {
        int prev = left;
        int cur = left+1;

        while(cur <= right) {
            if(array[cur] < array[left] && array[++prev] != array[cur]) {
                swap(array,prev,cur);
            }
            cur++;
        }
        swap(array,prev,left);
        return prev;
    }


    //优化快排 均匀分割

    private static int midTree(int[] array,int left,int right) {

        int mid = (left+right) / 2;

        if(array[left] < array[right]) {
            if(array[mid] < array[left]) {
                return left;
            }else if(array[mid] > array[right]) {
                return right;
            }else {
                return mid;
            }
        }else {
            if(array[mid] < array[right]) {
                return right;
            }else if(array[mid] > array[left]) {
                return left;
            }else {
                return mid;
            }
        }
    }


    //非递归快速排序
    public static void quickSort1(int[] array) {
        Deque<Integer> stack = new LinkedList<>();
        int left = 0;
        int right = array.length-1;
        int pivot = partition(array, left, right);


        //左边的区间
        if(pivot > left+1) {
            stack.push(left);
            stack.push(pivot-1);
        }

        //右边的区间
        if(pivot < right-1) {
            stack.push(pivot+1);
            stack.push(right);
        }

        while(!stack.isEmpty()) {
            right = stack.pop();
            left = stack.pop();
            pivot = partition(array, left, right);
            if(pivot > left+1) {
                stack.push(left);
                stack.push(pivot-1);
            }
            if(pivot < right-1) {
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }

}
